// 函数递归

#include<stdio.h>
#include<string.h>
//---------------------------------------------小节分割线--------------------------------------------
// 递归作用：把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
// 递归条件：
// 1.存在限制条件，当满足这个限制条件的时候，递归便不再继续。
// 2.每次递归调用之后越来越接近这个限制条件
// 练习1：接受一个整型值（无符号），按照顺序打印它的每一位。
// 例：输入：1234，输出 1 2 3 4
// void print(unsigned int n)
// {
//     if (n>9) // 如果n不是一位数，就去掉最后一位继续调用自己
//     {
//         print(n/10); // 这时候还没有打印
//     }
//     printf("%u ", n%10); // 打印当前的个位数
    
// }

// int main()
// {
//     unsigned int num = 1234;
//     //scanf("%u", &num);
//     print(num);
//     return 0;
// }
//---------------小分割线 >.< --------------------
// 每一次函数调用，都需要在栈区里分配一块空间
// 每一次调用test，就要在栈区内，申请一块当前函数的站帧空间，如果申请的太多了就会栈溢出
// 递归层次不能太深
// void test(int n)
// {
//     if (n < 10000)
//     {
//         test(n + 1);
//     }
    
// }

// int main()
// {
//     int a = 10;
//     test(1);
//     return 0;
// }
//---------------------------------------------小节分割线--------------------------------------------

// 练习2：编写函数不允许创建临时变量，求字符串的长度。
// 如果要使用临时变量的写法：
// int main()
// {
//     char arr[] = "abc";
//     // ['a']['b']['c']['\0']
//     printf("%d\n", strlen(arr));
//     return 0;
// }
// 思路：模拟实现一个strlen函数
// 但是函数中也不能使用计数器count，计算什么时候读到\0作为字符结尾
// my_stl("abc\0")→1+my_stl("bc\0")→1+1+my_stl("c\0")→1+1+1+my_stl("\0")→1+1+1+0
// int my_stl(char* str) // 字符串第一个字符的地址
// {
//     if (*str != '\0')  // 如果当前地址所对应的字符不是字符串结束符\0，就递归
//         return 1 + my_stl(str + 1); // 这里的str + 1是指当前的字符地址指向下一个位置
//     else
//         return 0;
// }
// int main()
// {
//     char arr[] = "abc";
//     // ['a']['b']['c']['\0']
//     printf("%d\n", my_stl(arr));
//     return 0;
// }
//---------------小分割线 >.< --------------------
// 练习3：求n的阶乘（不考虑栈溢出）
// int JieCheng(int n)
// {
//     if (n > 0)
//         return n * JieCheng(n - 1);
//     else
//         return 1;
// }

// int main()
// {
//     int n = 4;
//     printf("%d\n", JieCheng(n));
//     return 0;
// }
//---------------小分割线 >.< --------------------
// 练习4：求第n个斐波那契数。（不考虑溢出）
// int count = 0;//全局变量
// int fib1(int n) // 使用递归的方式，从后往前算，效率太低
// {
//     if(n == 3)
//         count++;
//     if (n <= 2)        
//         return 1;
//     else
//         return fib1(n - 1) + fib1(n - 2);
// }
// int fib2(int n)
// {
//     int ret1 = 1; // 1号位置，初始值为1
//     int ret2 = 1; // 2号位置，在1号位置之后，初始值为1
//     int result = 1; // 3号位置，在2号位置之后，也就是最终结果，等于前两个位置之和
//     // 这里如果n等于1或者2，不进入循环直接输出result就是1
//     // 如果n比2大就进入循环，n本身也就作为循环次数的计数器
//     while (n>2)
//     {
//         result = ret1 + ret2;
//         ret1 = ret2;
//         ret2 = result;
//         n--;
//     }
//     return result;
// }
// int main()
// {
//     int n = 40;
//     printf("%d\n", fib2(n));
//     // printf("count = %d\n", count);
//     return 0;
// }
// 这里有个问题就是，使用count计算第三个斐波那契数倍计算了多少次
// 发现有很多次的重复计算，所以这里直接使用公式进行递归就效率很低